Content-Type: multipart/signed; micalg=pgp-sha256;
	protocol="application/pgp-signature"; boundary="2j20lirfJqnP0rOh"


--2j20lirfJqnP0rOh
Content-Type: text/plain; charset="UTF-8"
Content-Disposition: inline

I'm pleased to announce availability of the next installment in the
S-unit-attacks saga: a new 59-page paper "Fast norm computation in
smooth-degree Abelian number fields", to appear at the upcoming
Algorithmic Number Theory Symposium.

This paper is backed by an "abelianfields" software package with
thousands of lines of Sage scripts testing the paper's main algorithms,
and a smaller "cyclo2power" C software package demonstrating concrete
speeds achieved for the easier case of power-of-2 cyclotomic fields.

The computational bottleneck addressed here is computing norms of many
small number-field elements. This is one of the central bottlenecks in
filtered-S-unit attacks against Ideal-SVP. It is also one of the central
bottlenecks in traditional class-group and unit-group computations, two
of the main tasks of computational algebraic number theory. There are
decades of earlier literature on algorithms handling this bottleneck for
general number fields.

The new paper and software show how to handle this bottleneck much more
efficiently for smooth-degree cyclotomic fields than any approach known
for general number fields. Concretely, the speedup factor is above
100000 at sizes of cryptographic interest.

Major contributions to this speedup include automorphisms (trivially)
and subfields (the main topic of the paper). Further details, including
the paper and the software, are available here:

   https://s-unit.attacks.cr.yp.to/norms.html

One should not think that this speedup is appearing all at once out of
nowhere; see the paper for credits to the relevant literature.

More broadly, there is already a long history in algebraic number theory
of problems that have been intensively studied for general number fields
and shown to have particularly efficient solutions for the extreme case
of cyclotomic fields. For examples and references, see Section 2.6 of
the following paper:

   https://ntruprime.cr.yp.to/latticerisks-20211031.pdf

For the relevance of cyclotomic weaknesses to the management of risks in
post-quantum cryptography, see Sections 1.3, 2.3, and 2.5 of that paper.

---D. J. Bernstein

-- 
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+unsubscribe@list.nist.gov.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/20220731143616.690268.qmail%40cr.yp.to.

--2j20lirfJqnP0rOh
Content-Type: application/pgp-signature; name="signature.asc"

-----BEGIN PGP SIGNATURE-----

iQIzBAEBCAAdFiEE3QolqQXydru4e4ITsMANTjsOVFkFAmLmk2AACgkQsMANTjsO
VFkMCxAAzvreA5wp5dFlc/0ud3QRTCOKc4vMbhdU5GV3IQ1l240TMv0PkL5R0LyI
R1mew4YTFbl8Qs41EleHjXaC4a3F0r10uHqHCv7l2UgvYStuLWmI7zWLWGb367eO
ZNlF0HZ9mfJ2IkfzRXag9SH95EP69UOa77x5E7x9Fgffa8fSqKqbbR/FGmQ3g4V/
g4epLsotufKvpYX1EHVf07LjPp1WpOiprWNWEH9GRtbZySgsrlrKciXna4reUZ4r
5rt1o0bEhrOUXPezAF/6d0iJRXmzFCLzqda6fU0pMcKG2APLlrP/zVDvsgNhoZei
cRDfxnn68W/yvLKKGj456X9IEX4/oh8pt8eI7xlpkMTZjXrC5ApaG8qxVH8LbgeJ
pl1rYAlnJMjgprmQlKUVL/4eYa2KilmZR3iruK4r4KloHV8p3XFdoTuxWsV/0/yX
YkwCpDCYC+/OgxmKKov4oQnLay7lLeGVc2QDLUYjZs02W5cJGJhRtFrhA8r+Afl6
0p6Eg8ZCe7+axUBd9hGjb2HvGpLlO1ro6zusHnHqCVeuKAyMxt5cVlHyIDWwMYM8
Ek9c/6L/SWB7WMi01zG15BH22wIZlTAhcaPHYTvDgnXoHjCuQawAV8xUZQezg2fH
4mlMQ094Rtf9FPSb3nJqAv7pVq009LWaFtXSsF415sOli364748=
=+ZK9
-----END PGP SIGNATURE-----

--2j20lirfJqnP0rOh--